【题解】P6130 随机红包

2021/06/29 更新：添加了详细的推式子过程，以及修改了排版。

如果有人问我推过最恶心的式子是哪个，我会说是这题。

我就不打表找规律，推式子警告

我们设 $f(n,k,x)$ 表示有 $n$ 个人的情况下，第 $k$ 小的红包钱数大于 $x$ 的概率。这也等价于至少 $n-k+1$ 个红包的钱数大于 $x$ 的概率。这里推荐使用第二种定义，方便理解后面的递推边界。

那么，容易看出我们要求的答案 $ans(n,k)=\int_0^1f(n,k,x)dx$。

考虑 $f$ 的递推式，$n$ 个人时生成了 $n-1$ 个随机数，设这些随机数里最小的那个是 $v$。此时一定有一个金额为 $v$ 的红包，讨论 $v$ 和 $x$ 的大小关系：

如果 $v<x$，那么剩下 $n-1$ 个红包里就需要 $n-k+1$ 个红包大于 $x$；

如果 $v>x$，那么剩下 $n-1$ 个红包里就需要 $n-k$ 个红包大于 $x$。

再想想，“$1-v$ 块钱分成 $n-1$ 个红包有 $n-k+1$ 个红包大于 $x$”和“$1$ 块钱分成 $n-1$ 个红包有 $n-k+1$ 个红包大于 $\frac{x}{1-v}$”是一样的，可以理解为通货膨胀了（？）

还有一个问题，虽然随机数是均匀分布的，但 $n-1$ 个随机数中的最小值 $v$ 可不是均匀分布的。我们要求出这个最小值小于 $v$ 的概率是 $1-(1-v)^{n-1}$，然后对它求导得到 $(n-1)(1-v)^{n-2}$，这个可以认为是最小值为 $v$ 的相对概率

综合上述讨论，可以得到 $f$ 的递推式

$\begin{aligned} &f(n,k,x)\\ =&(n-1)\int_0^x(1-v)^{n-2}f(n-1,k-1,\frac{x}{1-v})dv\\ +&(n-1)\int_x^1(1-v)^{n-2}f(n-1,k,\frac{x}{1-v})dv \end{aligned}$

开始积分

$\begin{aligned} &\int_0^1f(n,k,x)dx\\ =&(n-1)\int_0^1\int_0^x(1-v)^{n-2}f(n-1,k-1,\frac{x}{1-v})dvdx\\ +&(n-1)\int_0^1\int_x^1(1-v)^{n-2}f(n-1,k,\frac{x}{1-v})dvdx \end{aligned}$

设 $t=\frac{x}{1-v}$ 然后化简一波，此处省略去了漫长的计算过程

$\begin{aligned} &\int_0^1f(n,k,x)dx\\ =&\frac{n-1}{n}\int_0^{+\infty} (1-\frac{1}{(t+1)^n})f(n-1,k-1,t)dt\\ +&\frac{n-1}{n}\int_0^{+\infty} \frac{1}{(t+1)^n}f(n-1,k-1,t)dt \end{aligned}$

注意这里积分上界变成了 ${+\infty}$，不是 $1$，因为 $t$ 的范围可以到正无穷大，而且当 $k=n+1,x>1$ 时 $f(n,k,x)$ 仍然有意义且值为 $1$，所以一定要积到正无穷大！下面推边界的时候也有这方面的说明

貌似得到了更复杂的式子，出现了 $\frac{1}{(t+1)^n}$ 这个因子，我们用同样的方法继续积分看看

$\begin{aligned} &\int_0^{+\infty} \frac{1}{(x+1)^{(n+1)}}f(n,k,x)dx\\ =&\frac{n-1}{n}\int_0^{+\infty} (\frac{1}{(t+1)^n}-\frac{1}{(2t+1)^n})f(n-1,k-1,t)dt\\ +&\frac{n-1}{n}\int_0^{+\infty} \frac{1}{(2t+1)^n}f(n-1,k-1,t)dt \end{aligned}$

事情逐渐清晰起来，可以猜想并证明：

$\begin{aligned} &\int_0^{+\infty} \frac{1}{(lx+1)^{(n+1)}}f(n,k,x)dx\\ =&\frac{n-1}{n}\int_0^{+\infty} (\frac{1}{(lt+1)^n}-\frac{1}{((l+1)t+1)^n})f(n-1,k-1,t)dt\\ +&\frac{n-1}{n}\int_0^{+\infty} \frac{1}{((l+1)t+1)^n}f(n-1,k-1,t)dt \end{aligned}$

这回可以递推了。设

$P(n,k,l)=\int_0^{+\infty} \frac{1}{(lx+1)^{(n+1)}}f(n,k,x)dx$

则有

$P(n,k,l)=\frac{n-1}{n}(P(n-1,k-1,l)-P(n-1,k-1,l+1)+P(n-1,k,l+1))$

递推边界通过 $P$ 和 $f$ 的定义可以计算：

$P(n,k,l) = \begin{cases} 0, & k=0; \\ \int_0^{+\infty} (lx+1)^{-n-1}dx=\frac{1}{ln}, & k=n+1;\\ \int_0^1 (lx+1)^{-2}dx=\frac{1}{l+1}, & n=1;\\ \end{cases}$

这里为什么 $n=1$ 时积到 $1$ 而 $k=n+1$ 时要积到 ${+\infty}$ 呢，因为 $x>1$ 时 $f(1,1,x)=0$，但是 $k=n+1$ 时 $f(n,k,x)$ 表示的是至少 $0$ 个红包大于 $x$ 的概率，那么无论 $x$ 为何值 $f(n,k,x)$ 的值都为 $1$

最终答案就是 $P(n,k,0)$。

那么这玩意怎么化简呢

首先我们看着 $\frac{n-1}{n}$ 这个因子很难受，不妨修改一下 $P$ 的定义，用 $P(n,k,l)$ 表示之前 $nP(n,k,l)$ 表示的意思，那么递推式和边界都要修改，顺便还能把递推式改为等价的更简洁的形式

$P(n,k,l) = \begin{cases} 0, & n=0,k\le0; \\ \frac{1}{l}, & n=0,k>0;\\ P(n-1,k-1,l)-P(n-1,k-1,l+1)+P(n-1,k,l+1), & n>0 \end{cases}$

此时 $ans(n,k)=\frac{1}{n}P(n,k,0)$。

假设从 $P(n,k,0)$ 递归到 $n=0$ 共调用了 $a$ 次 $P(n-1,k-1,l)$ 分支，$b$ 次 $P(n-1,k-1,l+1)$ 分支，$c$ 次 $P(n-1,k,l+1)$ 分支。需要满足 $a+b+c=n$，$a+b<k$。那么这部分的贡献就是 $\frac{n!(-1)^b}{a!b!c!(b+c)}$，总和为

$P(n,k,0)=\sum_{a+b+c=n,a+b<k} \frac{n!(-1)^b}{a!b!c!(b+c)}$

继续化简

$\begin{aligned} P(n,k,0)=&\sum_{a+b+c=n,a+b<k} \frac{n!(-1)^b}{a!b!c!(b+c)}\\ =&\sum_{a=0}^{k-1} \frac{n!}{a!(n-a)}\sum_{b=0}^{k-a-1} (-1)^b\frac{1}{b!(n-a-b)!}\\ =&\sum_{a=0}^{k-1} \frac{n!}{a!(n-a)!(n-a)}(-1)^{k-a-1}C(n-a-1,k-a-1)\\ =&\frac{n!}{(n-k)!}\sum_{a=0}^{k-1} \frac{(-1)^{k-a-1}}{(n-a)^2a!(k-a-1)!}\\ =&\frac{n!}{(n-k)!}\frac{1}{(k-1)!}\sum_{a=0}^{k-1} (-1)^{k-a-1}C(k-1,a)(a-n)^{-2}\\ =&\frac{n!}{(n-k)!}\frac{1}{(k-1)!}\sum_{a=0}^{k-1} (-1)^{k-a-1}C(k-1,a)\sum_{j=0}^{\infty}C(-2,j)a^j(-n)^{-2-j}\\ =&\frac{n!}{(n-k)!}\sum_{j=0}^{\infty}C(-2,j)(-n)^{-2-j}\frac{1}{(k-1)!}\sum_{a=0}^{k-1} (-1)^{k-a-1}C(k-1,a)a^j\\ =&\frac{n!}{(n-k)!}\sum_{j=0}^{\infty}(j+1)n^{-2-j}S_2(j,k-1) \end{aligned}$

记 $G_m(x)$ 是第二类斯特林数第 $m$ 列的普通生成函数，$G_m'(x)$ 为其导数。我们有：

$G_m(x)=\sum_{i=0}^\infty S_2(i,m)x^i=\prod_{j=1}^m\frac{x}{1-jx}$

$G_m'(x)=\sum_{j=1}^m\frac{1}{x(1-jx)}G_m(x)$

原式可以写成生成函数的形式：

$\begin{aligned} P(n,k,0)=&\frac{n!}{(n-k)!}\sum_{j=0}^{\infty}(j+1)n^{-2-j}S_2(j,k-1)\\ =&\frac{n!}{(n-k)!} (n^{-3}G_{k-1}'(\frac{1}{n})+n^{-2}G_{k-1}(\frac{1}{n}))\\ =&\frac{n!}{(n-k)!} n^{-2} (1+\sum_{j=1}^{k-1}\frac{n}{n-j})G_{k-1}(\frac{1}{n})\\ =&\frac{n!}{(n-k)!} n^{-1} (\sum_{l=n-k+1}^{n}\frac{1}{l})\prod_{j=1}^{k-1}\frac{1}{n-j}\\ =&\sum_{l=n-k+1}^{n}\frac{1}{l} \end{aligned}$

这回可以快速计算多组询问了。别忘了除以 $n$！！

$ans(n,k)=\frac1n\sum_{l=n-k+1}^n\frac1l$

提醒：比赛时遇到这种题果断打表找规律。